Design an iterator that supports the peek operation on a list in addition to the hasNext and the next operations.
Implement the PeekingIterator class:
PeekingIterator(int[] nums)Initializes the object with the given integer arraynums.int next()Returns the next element in the array and moves the pointer to the next element.bool hasNext()Returnstrueif there are still elements in the array.int peek()Returns the next element in the array without moving the pointer.
Example 1:
Input ["PeekingIterator", "next", "peek", "next", "next", "hasNext"] [[[1, 2, 3]], [], [], [], [], []] Output [null, 1, 2, 2, 3, false] Explanation PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3] peekingIterator.next(); // return 1, the pointer moves to the next element [1,2,3]. peekingIterator.peek(); // return 2, the pointer does not move [1,2,3]. peekingIterator.next(); // return 2, the pointer moves to the next element [1,2,3] peekingIterator.next(); // return 3, the pointer moves to the next element [1,2,3] peekingIterator.hasNext(); // return False
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 1000- All the calls to
nextandpeekare valid. - At most
1000calls will be made tonext,hasNext, andpeek.
Follow up: How would you extend your design to be generic and work with all types, not just integer?
peek() before next() vs next() before peek().Average Rating: 4.83 (41 votes)
Solution
Overview - What is an Iterator?
Feel free to skip this section if you're already familiar with this material. We have included it, as this is a beginners question on iterators.
If you've heard of Iterators, you might assume they're simply a way of iterating over indexed or finite data structures. You've probably used them in loops, e.g. for item in items: in Python or for (int num : nums) in Java.
This may make it seem strange that we would need a .peek() on an Iterator. After all, couldn't we just convert our data structure into an array and use indexing to peek?
But actually Iterators have some interesting properties that make them widely useful for not only indexed collections (e.g. Array) and other finite data structures (e.g. LinkedList or HashMap keys), but also for (possibly-infinite) generated data. We'll look at an example of that soon.
The first property of an Iterator that we'll looked at is that it only needs to know how to get the next item. It doesn't need to store the entire data in memory if we don't need the entire data structure. For massive data structures, this is invaluable!
For example consider a linked list Iterator. We'll use Python as it's nice and compact. The same ideas apply to Java and C++:
class LinkedListIterator:
def __init__(self, head):
self._node = head
def hasNext(self):
return self._node is not None
def next(self):
result = self._node.value
self._node = self._node.next
return result
Notice how we store the head at the start, but as items are consumed, we discard the current one and replace it with the item in the node after?
This means that if we're simply iterating a Linked List, and don't ever need to go back to the head, then we only need to keep one value around at a time.
Another really interesting property of Iterators is that they can represent sequences without even using a data structure!
For example consider a range Iterator:
class RangeIterator:
def __init__(self, min, max):
self._max = max
self._current = min
def hasNext(self):
return self._current < self._max
def next(self):
self._current += 1
return self._current - 1
If we simply converted this to an Array, we'd need to allocate a large chunk of memory if min and max are far apart. For the most part, this would probably be wasted space.
However, by using an Iterator, we can use features like for i in range(40, 20000000) while still retaining the O(1) space of classic for (int i = min; i < max; i++) style loops seen in other languages.
Our final property is one that we couldn't even do by copying values into an Array—handling an infinite sequence. For example consider an Iterator of squares:
class SquaresIterator:
def __init__(self):
self._n = 0
def hasNext(self):
# It continues forever,
# so definitely has a next!
return True
def next(self):
result = self._n
self._current += 1
return result ** 2
Notice that because .hasNext() always returns True, this Iterator will never run out of items. And this is to be expected, there's always another square after the previous, so our Iterator can give as many as we ask from it.
Now that we've looked at why Iterators are awesome, let's consider what they are at a base level.
An Iterator only provides two methods:
-
.next()This returns the next item in the sequence. You can't assume that this item actually "exists" yet, it might be created when you call.next(), or it might already exist in a data structure that you have anIteratorover.Once
.next()is called, it will update the state of theIterator. This means once you've got a value from.next()you won't be able to get the same value again. Therefore, if you don't store or process the value you got from theIteratorthen it's possibly gone forever! -
.hasNext()This returns whether or not another item is available. For example, an arrayIteratorshould returnFalseif we're at the end of the array. But for anIteratorthat can produce items indefinitely, such as our square generator above, it might never returnFalse.
A further property of Iterators is that they provide a clean interface for the code using them. Without Iterators, Linked List's, for example, tend to be particularly messy, as the code for traversing them gets muddled within the application code. With an Iterator, the external code doesn't even know how the underlying data structure works. For all it knows, the data could be coming from a Linked List, an Array, a Tree, a State Machine, a clever number generator, a file reader, a robot sensor, etc.
Not having to deal with nodes, state, indexes, etc leads to clean code. We call this the Iterator Pattern, and it is one of the most important design patterns for a software engineer to know.
As shown above, with only two methods, we get a lot of benefit (e.g. infinite sequences) and increased performance (e.g. not expanding sequences like range into arrays). We also get a nice way of separating the underlying data structure from the code that uses it.
Approach 1: Saving Peeked Value
Intuition
Each time we call .next(...), a value is returned from the Iterator. If we call .next(...) again, a new value will be returned. This means that if we want to use a particular value multiple times, we had better save it.
Our .peek(...) method needs to call .next(...) on the Iterator. But because .next(...) will return a different value next time, we need to store the value we peeked so when .next(...) is called we return the correct value.
Algorithm
Complexity Analysis
-
Time Complexity : All methods: O(1).
The operation performed to update our peeked value are all O(1).
The actual operations from
.next()are impossible for us to analyse, as they depend on the givenIterator. By design, they are none of our concern. Our addition to the time is only O(1) though. -
Space Complexity : All methods: O(1).
Like with time complexity, the
Iteratoritself is probably using memory in its own implementation. But again, this is not our concern. Our implementation only uses a few variables, so is O(1).
Approach 2: Saving the Next Value
Intuition
Instead of only storing the next value after we've peeked at it, we can store it immediately in the constructor and then again in the next(...) method. This greatly simplifies the code, because we no longer need conditionals to check whether or not we are currently storing a peeked at value.
Algorithm
Note that in the Java code, we need to be careful not to cause an exception to be thrown from the constructor, in the case that the Iterator was empty at the start. We can do this by checking it has a next, and if it doesn't, then we set the next variable to null.
Complexity Analysis
-
Time Complexity : All methods: O(1).
Same as Approach 1.
-
Space Complexity : All methods: O(1).
Same as Approach 1.
The Follow Up
For the most part, our code would work fine if we replaced integers with another data type (e.g. strings).
There is one case where this does not work, and that's if the underlying Iterator might return null/ None from .next(...) as an actual value. If our code is using null to represent an exhausted Iterator, or to represent that we don't currently have a peeked value stored away (as in Approach 1), then the conditionals in PeekingIterator will not behave as expected on these values coming out of the underlying Iterator.
We can solve it by using separate boolean variables to state whether or not there's currently a peeked value or the Iterator is exhausted, instead of trying to infer this information based on null status of value variables.
In Java, you can also use generics on your Iterator.
February 26, 2020 4:38 AM
class PeekingIterator implements Iterator<Integer> {
private final Iterator<Integer> iterator;
private boolean hasPeeked;
private Integer peekedElement;
public PeekingIterator(Iterator<Integer> iterator) {
this.iterator = iterator;
}
public Integer peek() {
if (!hasPeeked) {
hasPeeked = true;
peekedElement = iterator.next();
}
return peekedElement;
}
@Override
public Integer next() {
if (!hasPeeked) {
return iterator.next();
}
Integer result = peekedElement;
peekedElement = null;
hasPeeked = false;
return result;
}
@Override
public boolean hasNext() {
return hasPeeked || iterator.hasNext();
}
}
February 8, 2021 6:30 PM
Cheating with Python3 queue
from collections import deque
class PeekingIterator:
q: deque = deque()
def __init__(self, iterator):
"""
Initialize your data structure here.
:type iterator: Iterator
"""
while iterator.hasNext():
self.q.append(iterator.next())
def peek(self):
"""
Returns the next element in the iteration without advancing the iterator.
:rtype: int
"""
return self.q[0]
def next(self):
"""
:rtype: int
"""
return self.q.popleft()
def hasNext(self):
"""
:rtype: bool
"""
return len(self.q) > 0
February 8, 2021 3:39 PM
I have a couple of comments on the "Follow up" for java:
-
If the underlying
Iteratorreturns null, then we can useOptional<Integer>to represent the last peeked value. -
I think that there is another case in which the proposed solution will not work properly: our
PeekingIteratorhas private field that is a reference to the passediterator, and if the caller of our function callsiterator.next()on the passediteratorafter instantiating aPeekingIterator, then the we cannot guarantee the required behavior. The only solution to prevent this problem (IMHO) is to make a private copy of the values of the passediteratorand to use those. However, even this solution has a drawback, that is it will consume the passediterator.
My solution with Optional:
import java.util.Optional;
import java.util.NoSuchElementException;
class PeekingIterator implements Iterator<Integer> {
private final Iterator<Integer> iterator;
private Optional<Integer> peeked = Optional.empty();
public PeekingIterator(Iterator<Integer> iterator) {
this.iterator = iterator;
}
// Returns the next element in the iteration without advancing the iterator.
public Integer peek() {
if (hasNext()) {
if (peeked.isPresent())
return peeked.get();
else {
Integer val = iterator.next();
peeked = Optional.ofNullable(val);
return val;
}
} else
throw new NoSuchElementException();
}
// hasNext() and next() should behave the same as in the Iterator interface.
// Override them if needed.
@Override
public Integer next() {
if (hasNext()) {
if (peeked.isPresent()) {
Integer val = peeked.get();
peeked = Optional.empty();
return val;
} else
return iterator.next();
} else
throw new NoSuchElementException();
}
@Override
public boolean hasNext() {
return iterator.hasNext() || peeked.isPresent();
}
}
September 18, 2020 1:35 AM
It seems this part
def next(self):
result = self._n
self._current += 1
return result ** 2
Should be like this :
def next(self):
result = self._n
self._n += 1
return result ** 2
The value of self._n needs to be updated after each next() call.
June 17, 2020 10:07 AM
nitpick in python 3 range is not a iterator but it's a sequence
https://treyhunner.com/2018/02/python-range-is-not-an-iterator/
(list, tuple are also sequences but range gives answer computationally)
Last Edit: February 8, 2021 9:56 PM
All parts are good except:
we don't need to throw the NSE exception explicitly, right? Because when you call iterator.next(), it will throw an NSE if there is no next element by its implementation. Below is my code, of a generalized form with a flag:
class PeekingIterator implements Iterator<Integer> {
// saving peeked value
// time: O(1)
// memory: O(1)
private Iterator<Integer> iterator;
private boolean peeked;
private Integer peekedValue;
public PeekingIterator(Iterator<Integer> iterator) {
this.iterator = iterator;
}
public Integer peek() {
if (!peeked) {
peekedValue = iterator.next();
peeked = true;
}
return peekedValue;
}
@Override
public Integer next() {
if (peeked) {
Integer toReturn = peekedValue;
peeked = false;
return toReturn;
}
return iterator.next();
}
@Override
public boolean hasNext() {
return peeked || iterator.hasNext();
}
}
January 3, 2021 4:43 AM
should be an Easy
February 9, 2021 8:49 AM
Python ~100% [1 min solution - Hacked it! :p ]
class PeekingIterator:
START_INDEX = 0
def __init__(self, iterator):
"""
Initialize your data structure here.
:type iterator: Iterator
"""
self.iterator = iterator
def peek(self):
"""
Returns the next element in the iteration without advancing the iterator.
:rtype: int
"""
if len(self.iterator.v) > 0:
return self.iterator.v[PeekingIterator.START_INDEX]
def next(self):
"""
:rtype: int
"""
if len(self.iterator.v) > 0:
return self.iterator.v.pop(PeekingIterator.START_INDEX)
def hasNext(self):
"""
:rtype: bool
"""
return len(self.iterator.v) != 0
June 28, 2020 12:32 PM
python Iterator implementation is naive. Could you post C++ Iterator solution.
x
/* * Below is the interface for Iterator, which is already defined for you. * **DO NOT** modify the interface for Iterator. * * class Iterator { * struct Data; * Data* data; * public: * Iterator(const vector<int>& nums); * Iterator(const Iterator& iter); * * // Returns the next element in the iteration. * int next(); * * // Returns true if the iteration has more elements. * bool hasNext() const; * }; */class PeekingIterator : public Iterator {private: int nextData; bool hasNextData; public: PeekingIterator(const vector<int>& nums) : Iterator(nums) { hasNextData = Iterator::hasNext(); if(hasNextData) nextData = Iterator::next(); } int peek() { return nextData; } int next() { int res = nextData; hasNextData = Iterator::hasNext(); if(hasNextData) nextData = Iterator::next(); return res; } bool hasNext() const { return hasNextData; }};